/*
* 在计算机科学中，一个图就是一些顶点的集合，这些顶点通过一系列"边-结对（连接）"。顶点用圆圈表示，边就是这些圆圈之间的连线。顶点之间通过边连接。
* 边可以有权重（weight），即每一条边会被分配一个正数或者负数值。考虑一个代表航线的图。各个城市就是顶点，航线就是边。那么边的权重可以是飞行时间，或者机票价格。
*
* 特殊的图:
*       完全图: n个顶点的完全图记做Kn，是指每对不同顶点之间都恰好只有一条边；
*       圈图: n个顶点的圈图记做Cn，顶点之间以此建立边的关系，比如三角形、正方形、正五边形等；
*       轮图: 向圈图Cn添加一个顶点，并把这个新顶点与Cn中每一个顶点向连接，就得到轮图，记做Wn；
* 图的表示:
*       邻接表: 表示不带多重边的图的一种方式是列出这个图的所有边，另外可以列出图中每个顶点与其他顶点的相邻情况，这种表示方法叫做邻接表；
*       邻接矩阵: 如果图中存在很多边，那么使用领接表时就不便于执行图算法，此时可以使用矩阵来表示图，这种表示方法称为邻接矩阵；
*/

// 带权有向图最短路径问题：如果从有向图中某一顶点(称为源点)到达另一顶点(称为终点)的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小。

var VNUM = 6; // 顶点数
var MV = 65536; // 最大数值

// 邻接矩阵定义图  MV表示顶点间没有变，不邻接
/*
*   0 1 2 3 4 5
* 0 0   N      
* 1 N 0   N N N
* 2 N N 0 N   N
* 3 N N   0   N
* 4 N N N N 0 N
* 5 N N N N   0
*/
var Matrix = [
    [0, 10, MV, 30, MV, 20],
    [MV, 0, 50, MV, MV, MV],
    [MV, MV, 0, MV, 10, MV],
    [MV, MV, 20, 0, 60, MV],
    [MV, MV, MV, MV, 0, MV],
    [MV, MV, MV, MV, 50, 0],
];

// 单源最短路径问题：迪杰斯特拉算法O(n*n)
console.log("----迪杰斯特拉算法----");
var PathDij = []; // 辅助数组
var Dist = []; // 存放最短路径，权值
var Mark = []; // 标记数组
function initDijkstraHelperArr() {
    PathDij.length = 0;
    Dist.length = 0;
    Mark.length = 0;
    for (let i = 0; i < VNUM; i++) {
        PathDij.push(0);
        Dist.push(0);
        Mark.push(0);
    }
}
initDijkstraHelperArr();
function Dijkstra(sv) {
    if (sv < 0 || sv >= VNUM) {
        return;
    }
    let i = 0;
    let j = 0;
    // 初始化辅助数组,先将从源点sourcePoint到达其他所有点的距离记录下来
    for (i = 0; i < VNUM; i++) {
        Dist[i] = Matrix[sv][i];
        Mark[i] = 0;
        // 因为一开始都是从源点到点i，因此路径的父节点全部都是源点sourcePoint
        if (Dist[i] < MV) {
            PathDij[i] = sv;
        }
        else {
            PathDij[i] = -1;
        }
    }
    console.log(Dist);
    // 这个算法是从源点开始计算的,所以源点一开始就在集合s当中
    Mark[sv] = 1;
    // 循环求得sv到各个顶点的最短路径
    for (i = 0; i < VNUM; i++) {
        let min = MV; //记录最短路(一开始先置为最大）
        let index = sv; //源点为最开始的点

        //寻找从源点sourcePoint到不属于s集合的点u的最短距离的点
        for (j = 0; j < VNUM; j++) {
            if (!Mark[j] && (Dist[j] < min)) {
                min = Dist[j];
                index = j;
            }
        }
        // 将节点u加入到s集合当中
        Mark[index] = 1;

        // 以节点u为父节点，下一跳可前往位置
        for (j = 0; j < VNUM; j++) {
            //若点j不属于集合s，并且点u到点j之间存在道路
            if (!Mark[j] && Matrix[index][j] != MV) {
                // 若通过点u前往点j的路程比直接前往点j的路程要短（也有可能是通过点u前往到点j的路程比之前计算出的前往点j的路程要短）
                // 则记录这个通向点j的路程,并且将点u记录为前往点j的父节点
                if (min + Matrix[index][j] < Dist[j]) {
                    Dist[j] = min + Matrix[index][j];
                    PathDij[j] = index;
                }
            }
        }
        console.log(Dist);
    }
    // 打印最短路径及顶点
    for (i = 0; i < VNUM; i++) {
        let p = i;
        // 顶点sv到其它顶点的路径
        console.log(`${sv} -> ${p}: ${Dist[p]}`);
        // 最短路径顶点关系
        let str = "";
        do {
            str = ` -> ${p}` + str;
            p = PathDij[p];
        } while (p != sv);

        console.log(`${p}${str}\n`);
    }
}
Dijkstra(0);

// 所有顶点之间的最短路径: 弗洛伊德算法O(n*n*n)
console.log("----弗洛伊德算法----");
var P = [];       // 存放最短路径当前顶点
var A = [];       // 存放最短路径
function initFloydHelperArr() {
    P.length = 0;
    A.length = 0;
    for (let i = 0; i < VNUM; i++) {
        P[i] = [];
        A[i] = [];
        for (let j = 0; j < VNUM; j++) {
            P[i].push(0);
            A[i].push(0);
        }
    }
}
initFloydHelperArr();
function Floyd() {
    let i = 0;
    let j = 0;
    let k = 0;
    // 2次嵌套循环，初始化路径和顶点
    for (i = 0; i < VNUM; i++) {
        for (j = 0; j < VNUM; j++) {
            A[i][j] = Matrix[i][j];          // 初始化路径
            P[i][j] = j;                     // 保存当前顶点
        }
    }
    // 3次嵌套循环，试探求最短路径
    for (i = 0; i < VNUM; i++) {
        for (j = 0; j < VNUM; j++) {
            for (k = 0; k < VNUM; k++) {
                if ((A[j][i] + A[i][k]) < A[j][k]) {
                    A[j][k] = A[j][i] + A[i][k];     // 最短路径
                    P[j][k] = P[j][i];               // 标记当前顶点
                }
            }
        }
    }
    // 显示最短路径
    for (i = 0; i < VNUM; i++) {
        for (j = 0; j < VNUM; j++) {
            let p = -1;
            // 顶点i到j的路径
            console.log(`${i} -> ${j}: ${A[i][j]}`);
            let str = i + "";
            p = i;
            do {
                p = P[p][j];
                str += ` -> ${p}`;
            } while (p != j);
            console.log(`${str}\n`);
        }
    }
}
Floyd();